package dp01;

/**
 * 题目：买卖股票的最佳时机 |
 * 题目链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/description/
 * dp[i]表示到i节点时为最大利润，有两个状态：当前值减去前面最小值，或者上一个就是利润最大值
 */
public class Solution12 {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[] dp = new int[n];
        dp[0] = 0;
        int min = prices[0];
        for (int i = 1; i < n; i++) {
            if (prices[i] > min) {
                dp[i] = Math.max(prices[i] - min, dp[i - 1]);
            } else {
                min = prices[i];
            }
        }
        int ret = -Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            ret = Math.max(ret,dp[i]);
        }
        return ret;
    }
}
